package lc_剑指_Offer_II_086_分割回文子字符串;

import java.util.ArrayList;
import java.util.List;

public class Solution {

	public String[][] partition(String s) {
		List<List<String>> ans = new ArrayList<>();
		char[] cs = s.toCharArray();
		int n = s.length();
		boolean[][] h = new boolean[n][n];
		for (int i = 0; i < n; i++) {
			for (int j = i; j >= 0; j--) {
				if (cs[j] == cs[i] && (i - j <= 1 || h[j + 1][i - 1])) {
					h[j][i] = true;
				}
			}
		}
		f(0, new ArrayList<>(), ans, n, cs, h);
		String[][] ret = new String[ans.size()][];
		for (int i = 0; i < ans.size(); i++) {
			ret[i] = ans.get(i).toArray(String[]::new);
		}
		return ret;
	}

	private void f(int id, List<String> list, List<List<String>> ans, int n, char[] cs, boolean[][] h) {
		if (id == n) {
			ans.add(new ArrayList<>(list));
			return;
		}
		for (int i = id + 1; i <= n; i++) {
			if (h[id][i - 1]) {
				list.add(new String(cs, id, i - id));
				f(i, list, ans, n, cs, h);
				list.remove(list.size() - 1);
			}
		}
	}
}